package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 剑指 Offer 57 - II. 和为s的连续正数序列
 *
 * @author weiruibai.vendor
 * Date: 2022/9/6 14:25
 */
public class Solution_57_II {

    public static void main(String[] args) {
        Solution_57_II solution = new Solution_57_II();
        int target = 9;
        solution.findContinuousSequence(target);
    }

    /**
     * eg: target = 9;
     * sumArray={0,1,3,6,10,15}
     * 1、固定左边界L=0(0,1,2...),有边界R=L+1
     * 2、当sub<target时，依次扩大R,直到sub值有以下情况
     * 2.1 sub==target 且个数大于1，收集答案，同时L++
     * 2.2 sub>target时，说明R过大，只能让L++;
     * 2.3 sub<target时，R++;
     *
     * @param target
     * @return
     */
    public int[][] findContinuousSequence(int target) {
        // (1+N)*N/2 = target
        int N = target % 2 == 0 ? target / 2 + 1 : target / 2 + 2;
        int[] sumArray = new int[N];
        sumArray[0] = 0;
        for (int i = 1; i < N; i++) {
            sumArray[i] += sumArray[i - 1] + i;
        }
        List<int[]> ans = new ArrayList<>();// ！！！
        int[] tmp;
        int L = 0, R = 1;
        int sub;
        while (R > L && R < N && L < N) {
            sub = sumArray[R] - sumArray[L];
            if (sub == target && R - L > 1) {// R - L > 1因为保证元素个数大于1
                tmp = new int[R - L];
                int k = 0;
                for (int i = L + 1; i <= R; i++) {// 注意这里，L+1
                    tmp[k++] = i;
                }
                ans.add(tmp);
                L++;
                R = L + 1;
            } else if (sub < target) {
                //
                R++;
            } else {
                L++;
            }
        }
        int[][] res = new int[ans.size()][];
        for (int i = 0; i < res.length; i++) {
            res[i] = ans.get(i);
        }
        return res;
    }
}
